#include "sort.h"
#include <stdlib.h>
#include <string.h>
static int *array_temp = NULL;
static int len_temp = 0;
int merge(int *array, int len)
{
	if(len < 2){
		return 0;
	}
	int i = 0;
	int j = len/2;
	while(i<len/2 && j<len){
		if(array[i] <= array[j]){
			array_temp[i+j-len/2] = array[i];
			i ++;
		}else{
			array_temp[i+j-len/2] = array[j];
			j ++;
		}
	}
	if(i < len/2){
		memcpy(array_temp+i+j-len/2, array+i, sizeof(int)*(len/2-i));
	}else if(j < len){
		memcpy(array_temp+i+j-len/2, array+j, sizeof(int)*(len-j));
	}
	memcpy(array, array_temp, sizeof(int)*len);
	if(len == len_temp){
		free(array_temp);
	}
	return 0;
}
int merge_sort(int *array, int len)
{
	if(len < 2){
		return 0;
	}
	if(array_temp == NULL){
		array_temp = malloc(sizeof(int) * len);
		len_temp = len;
	}
	merge_sort(array, len/2);
	merge_sort(array+len/2, len-len/2);
	merge(array, len);
	return 0;
}

